home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / lisp / clisp-li.000 / clisp-li / clisp-1996-07-22 / queens / queens.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-19  |  1.7 KB  |  46 lines
  1. /* Compute the number of solutions to the n-queens problem on a nxn
  2.    checkboard. */
  3.  
  4. /* dynamic data structures not needed for such a simple problem */
  5. #define nmax 100
  6.  
  7. int queens (n)                /* function definition in traditional C style */
  8.   int n;
  9. { /* Compute the solutions of the n-queens problem. Assume n>0, n<=nmax.
  10.      We look for a function D:{1,...,n} -> {1,...,n} such that
  11.      D, D+id, D-id are injective. We use backtracking on D(1),...,D(n).
  12.      We use three arrays which contain information about which values
  13.      are still available for D(i) resp. D(i)+i resp. D(i)-i. */
  14.   int dtab[nmax]; /* values D(1),...D(n) */
  15.   int freetab1[nmax+1]; /* contains 0 if available for D(i) in {1,...,n} */
  16.   int freetab2[2*nmax+1]; /* contains 0 if available for D(i)+i in {2,...,2n} */
  17.   int freetab3a[2*nmax-1]; /* contains 0 if available for D(i)-i in {-(n-1),...,n-1} */
  18. #define freetab3 (&freetab3a[nmax-1])
  19.   /* clear tables */
  20.   { int i; for (i=1; i<=n; i++) { freetab1[i] = 0; } }
  21.   { int i; for (i=2; i<=2*n; i++) { freetab2[i] = 0; } }
  22.   { int i; for (i=-(n-1); i<n; i++) { freetab3[i] = 0; } }
  23.  {int counter = 0;
  24.   int i = 0; /* recursion depth */
  25.   int* Dptr = &dtab[0]; /* points to next free D(i) */
  26.   entry: /* enter recursion */
  27.     i++;
  28.     if (i > n)
  29.       { counter++; }
  30.       else
  31.       { int try;
  32.         for (try = 1; try <= n; try++)
  33.           { if (freetab1[try]==0 && freetab2[try+i]==0 && freetab3[try-i]==0)
  34.               { freetab1[try]=1; freetab2[try+i]=1; freetab3[try-i]=1;
  35.                 *Dptr++ = try;
  36.                 goto entry;
  37.                 comeback:
  38.                 try = *--Dptr;
  39.                 freetab1[try]=0; freetab2[try+i]=0; freetab3[try-i]=0;
  40.       }   }   }
  41.     i--;
  42.     if (i>0) goto comeback;
  43.   return counter;
  44. }}
  45.  
  46.